package org.niu.str;

import java.util.ArrayList;
import java.util.Stack;

public class GenerateParenthesis {
    ArrayList<String> ans = new ArrayList<>();
    StringBuilder s = new StringBuilder();
    public ArrayList<String> generateParenthesis (int n) {
        // write code here
        s.append('(');
        s.append(')');
        backtracking(n*2,s);
        return ans;
    }
    boolean isValid(StringBuilder s){
        Stack<Character> stack = new Stack<>();
        if(s.length() %2 != 0) return false;
        for (int i = 0; i < s.length(); i++) {
            if(stack.isEmpty()){
                if(s.charAt(i)=='(')
                    stack.push(s.charAt(i));
                else return false;
            }
            else if(stack.peek()=='('&&s.charAt(i)==')'){
                stack.pop();
            }else{
                stack.push(s.charAt(i));
            }
        }
        return stack.isEmpty();
    }
    void backtracking(int n,StringBuilder t){
        if(!isValid(t)){
            return;
        }
        if(isValid(t)&&t.length()==n){
            ans.add(new StringBuilder(t).toString());
            return;
        }
        for (int i = 0; i < 2*n; i++) {
            t.append(s.charAt(i%2));
            backtracking(n,t);
            t.deleteCharAt(t.length()-1);
        }
    }
}
